/*
    Aufgabe 3) Rekursion mit eindimensionalen Arrays
*/
import java.util.Arrays;

public class Aufgabe3 {

    private static int getMaxPairSum(int[] workArray, int start, int end) {
        if (start == end) return 0;
        int ownSum = workArray[start] + workArray[start + 1];
        int otherSum = getMaxPairSum(workArray, ++start, end);
        return Math.max(ownSum, otherSum);
    }

    private static int countValuesWithSmallerNeighbors(int[] workArray, int index) {
        if (index == workArray.length - 1) return 0;
        int isBigNeighbour =
                (workArray[index - 1] < workArray[index] &&
                 workArray[index + 1] < workArray[index]) ?
                1 : 0;
        int isNextBigNeighbour = countValuesWithSmallerNeighbors(workArray, ++index);
        return isBigNeighbour + isNextBigNeighbour;
    }


    private static int[] getArrayWithNegativeValues(int[] workArray, int index) {
        if (index == workArray.length - 1) return workArray;
        int[] negValues = workArray.clone();
        negValues[index] = Math.min(workArray[index], 0);
        return getArrayWithNegativeValues(negValues, ++index);
    }

    private static boolean containsValue(int[] workArray, int value) {
        if (workArray.length == 0) return false;

        int middle = workArray.length / 2;

        int[] leftWorkArray = Arrays.copyOfRange(workArray, 0, middle);
        int[] rightWorkArray = Arrays.copyOfRange(workArray, middle + 1, workArray.length);

        boolean self = workArray[middle] == value;
        boolean containedInLeft = containsValue(leftWorkArray, value);
        boolean containedInRight = containsValue(rightWorkArray, value);

        return self || containedInLeft || containedInRight;
    }
    
    public static void main(String[] args) {
        int[] array1 = {3, 1, 7, 9, 4, 10, 5, 3};
        System.out.println(getMaxPairSum(array1, 0, array1.length - 1));
        System.out.println(getMaxPairSum(array1, 4, array1.length - 1));
        System.out.println(getMaxPairSum(array1, 1, 3));
        System.out.println(getMaxPairSum(array1, 0, 2));
        System.out.println(getMaxPairSum(array1, 0, 1));
        System.out.println();

        int[] array2 = {3, 9, 7, 19, 8, 10, 6, 3, 11, 5};
        System.out.println(countValuesWithSmallerNeighbors(array2, 1));
        System.out.println(countValuesWithSmallerNeighbors(array2, 4));
        System.out.println(countValuesWithSmallerNeighbors(array2, 6));
        System.out.println(countValuesWithSmallerNeighbors(array2, 8));
        System.out.println();

        int[] array3 = {5, -3, 7, -15, 20, -5, 0, 14, 3, -2, -8};
        System.out.println(Arrays.toString(array3));
        System.out.println(Arrays.toString(getArrayWithNegativeValues(array3, 0)));
        System.out.println(Arrays.toString(getArrayWithNegativeValues(array3, 10)));
        System.out.println(Arrays.toString(getArrayWithNegativeValues(array3, 8)));
        System.out.println(Arrays.toString(getArrayWithNegativeValues(array3, 4)));
        System.out.println();

        int[] array4 = {2, 4, 7, 10, -10, 4, 0, 0, 27, 11, 4, 6};
        System.out.println(containsValue(array4, 11));
        System.out.println(containsValue(array4, 2));
        System.out.println(containsValue(array4, 25));
        System.out.println(containsValue(array4, 0));
        System.out.println(containsValue(array4, 14));
        System.out.println(containsValue(array4, 6));
        
      
        assert(getMaxPairSum(array1, 0, array1.length - 1) == 16);
        assert(getMaxPairSum(array1, 4, array1.length - 1) == 15);
        assert(getMaxPairSum(array1, 1, 3) == 16);
        assert(getMaxPairSum(array1, 0, 2) == 8);
        assert(getMaxPairSum(array1, 0, 1) == 4);
        
        assert(countValuesWithSmallerNeighbors(array2, 1) == 4);
        assert(countValuesWithSmallerNeighbors(array2, 4) == 2);
        assert(countValuesWithSmallerNeighbors(array2, 6) == 1);
        assert(countValuesWithSmallerNeighbors(array2, 8) == 1);

        assert (Arrays.equals(getArrayWithNegativeValues(array3, 0), new int[]{0, -3, 0, -15, 0, -5, 0, 0, 0, -2, -8}) == true);
        assert (Arrays.equals(getArrayWithNegativeValues(array3, 10), new int[]{5, -3, 7, -15, 20, -5, 0, 14, 3, -2, -8}) == true);
        assert (Arrays.equals(getArrayWithNegativeValues(array3, 8), new int[]{5, -3, 7, -15, 20, -5, 0, 14, 0, -2, -8}) == true);
        assert (Arrays.equals(getArrayWithNegativeValues(array3, 4), new int[]{5, -3, 7, -15, 0, -5, 0, 0, 0, -2, -8}) == true);

        assert (containsValue(array4, 11) == true);
        assert (containsValue(array4, 2) == true);
        assert (containsValue(array4, 25) == false);
        assert (containsValue(array4, 0) == true);
        assert (containsValue(array4, 14) == false);
        assert (containsValue(array4, 6) == true);
    }
}

/*
    Zusatzfrage 1: Wie könnte containsValue(...) optimiert werden, wenn die Vorbedinung ist, dass workArray aufsteigend sortiert ist?
        mit einem zusätzlichen Vergleich ob das mittlere Element größer oder kleiner als das gesuchte Element ist, kann
        das durchsuchen einer gesamten Hälfte erspart werden, indem nur in der Hälfte gesucht wird, in der sich das
        Element nur befinden kann
*/
